1. Field of the Invention
The present invention relates to an interpolation method and a data transformation system. Specifically, the invention relates to a data transformation system. More specifically, the invention relates to an interpolation method to be employed together with a look-up table (hereinafter also referred to as "LUT) in data transformation, such as color transformation or so forth, and a data transformation system which executes interpolation.
2. Description of the Related Art
For example, when an image synthesized on a personal computer is output by a printer, it becomes necessary to perform color transformation of luminance signals R, G, B as image data into color signals Y, M, C, or into signals further including K in addition to the foregoing color signals, according to necessity. It is known that an input space defined by the luminance signals and an output space defined by the color signals in the color transformation have a non-linear relationship. When the relationship between the input and the output spaces is non-linear as stated above, it is not easy to precisely make a model of the transformation of the input space into the output space so as to perform an arithmetic operation. Also, even when the model can be made with a certain level or precision, it is possible that an amount of arithmetic operation required for the transformation per se becomes significant. In order to solve the problems in the data transformation, it has been known to perform the data transformation simply by preliminarily providing a table storing output data corresponding to respective input data.
However, even in such method, when the input space consists of 256 density levels with respect to each of signals R, G, B, for example, and when there is provided the table storing data of the output space corresponding to all data of the input space, an amount of data to be stored in the table becomes significant. Thus, in view of the cost for memory for the table, it is not practical. As a measure for this, it has been known to take a sample of the input space at an appropriate interval and make the table with respect to only sample points for reducing the amount of data stored. In this method, a transformed output data for a point other than the sample point (hereinafter also referred to as a grid point) of the input space is derived by a linear interpolation employing the grid point data of the sample points.
A three dimensional LUT is used in a three-dimensional transformation, in which input and output has a non-linear relation, such as color transformation of the luminance signals R, G, B into the color signals Y, M, C, or signals including a color signal K in addition to the foregoing color signals for three colors to be used in the printer. Thus, the three-dimensional LUT stores transformation data (hereinafter also referred to as grid point data) corresponding to respective grid points of a three-dimensional cubic grid formed by the input luminance signals R, G, B. For input corresponding to the point other than respective grid point in the three-dimensional cubic grid, a linear interpolating operation is performed with respect to an interpolation space expressed as a predetermined shape of a solid body containing the point to be transformed and having a given number of grid points as vertexes to obtain an output (transformed data) corresponding to the input.
An arithmetic expression for interpolation in a linear interpolation can be generally expressed as follows: ##EQU1## wherein k is a number of grid points to be utilized for the interpolation, v.sub.ui is a value indicated by the data of grid point ui, and c.sub.i is a weighting coefficient.
For example, when k is eight, the interpolation to be performed becomes an eight point interpolation using eight grid point data. In this case, the interpolation space becomes cubic. On the other hand, when k is five, the interpolation to be performed becomes a five point interpolation using five grid point data. The shape of the solid body to express the interpolation space is then variable depending upon selection of the five grid points. When k is preliminarily determined as set forth above, and the input signals R, G, B are expressed as byte data, the grid point data v.sub.ui to be used are output from the LUT on the basis of the predetermined upper bits of the input signals R, G, B, and, on the other hand, the weighting coefficient c.sub.i in the foregoing expression is determined on the basis of the lower bit data indicative of a position of the input signals in the interpolation space, for example.
A manner of the operation of the interpolating arithmetic expression as set forth above may vary depending upon a region in the interpolation space where an interpolating objective point indicative of the position of the input signals is located. For instance, there are four cases; where the region where the interpolating objective point is located is the grid point in the solid body expressing the interpolation space, where the region is a line connecting the grid points, where the region is a plane defined by the lines connecting the grid points, and where the region is inside of the solid body (these regions will be hereinafter referred to as a calculation divided segment). Since the number of grid point data and/or weighting coefficient to be practically used in the interpolating operation is different in respective cases, the operation can be simplified corresponding to the number of the grid point data and the weighting coefficient to be actually used. More specifically, when the interpolating operation is performed by software, the number of times to make reference to the grid point data or so forth or number of times of arithmetic operation for addition, subtraction, multiplication, and division are differentiated in respect to the foregoing four cases. Therefore, depending upon the region where the interpolating objective point is located, the number of times of operations and so forth can be reduced. For example, when the interpolating objective point is located on the grid point, the number of times of performing the operation can be minimum. On the other hand, when the interpolating objective point is located on the line connecting the grid point, the number of times of performing the operation can be second smallest.
Accordingly, the degree of simplification of the overall interpolating operation is determined by the number of respective interpolating objective points included in respective calculation divided segments within interpolating objective points designated by overall input signals. Assuming that the space defined by the overall input data is fixed, relatively greater number of grid points, namely, greater amount of data to be stored in the table, increases the probability that the interpolating objective point is located on the grid point or on the line connecting the grid points to achieve a greater degree of simplification. However, the required capacity of the table memory is increased. On the other hand, depending upon the shape of the solid body selected as the interpolating space, the degree of simplification is variable. At any rate, employing a simplified interpolating arithmetic expression is effective for reducing the overall interpolating arithmetic operation while the degree of simplification is variable.